package com.study.tree;

import java.util.function.Consumer;

public class BinarySearchTree {

    private Node root;

    public void insert(Integer key){
        Node curP = root;
        Node cur = new Node(key);
        Node iterator = curP;
        while (iterator !=null){
            curP = iterator;
            if(iterator.key > key){
                iterator = iterator.left;
            }else {
                iterator = iterator.right;
            }
        }
        cur.parent = curP;
        if(curP == null){
            root = cur;
        }else if (curP.key > key){
            curP.left = cur;
        }else{
            curP.right = cur;
        }
    }
//    用 b 替代 a
    private void replace(Node a,Node b){
        if(a == root){
            root = b;
            if(b!=null) b.parent = null;
        }else if(a.parent.left == a){
            a.parent.left = b;
            if(b != null) b.parent = a.parent.left;
        }else{
            a.parent.right = b;
            if(b!=null) b.parent = a.parent.right;
        }
    }

    public void delete(Integer key){
        Node delNode = search(key);
        if(delNode == null) return;
        if(delNode.right == null){
            replace(delNode,delNode.left);
        }else if(delNode.left == null){
            replace(delNode,delNode.right);
        }else{
            Node min = minNode(delNode.right);
            if(min != delNode.right){
                replace(min,min.right);
//                处理删除结点的右子树
                min.right = delNode.right;
                delNode.right.parent = min;
            }
            replace(delNode,min);
//            处理删除结点的左子树
            min.left = delNode.left;
            delNode.left.parent = min;
        }
    }

    public Node search(Integer key){
        Node it = root;
        while (it != null){
            if(it.key == key) return it;
            if(it.key >= key) it = it.left;
            else it = it.right;
        }
        return null;
    }

    private Node minNode(Node p){
        Node iterator = p;
        Node res = null;
        while (iterator !=null ){
            res = iterator;
            iterator = iterator.left;
        }
        return res;
    }

    public void printInOrder(){
        inOrder(t -> System.out.println(t.key),root);
    }

    public void inOrder(Consumer<Node> consumer,Node start){
        if(start != null){
            inOrder(consumer,start.left);
            consumer.accept(start);
            inOrder(consumer,start.right);
        }
    }

    private static class Node {
        Node left;
        Node right;
        Node parent;
        Integer key;
        Node(Integer key){
            this.key = key;
        }
    }
    public static void main(String[] args){
        BinarySearchTree bst = new BinarySearchTree();
        bst.insert(2);
        bst.insert(6);
        bst.insert(4);
        bst.insert(7);
        bst.insert(17);
        bst.insert(16);
        bst.insert(22);
        bst.insert(2);
        bst.insert(4);
        bst.printInOrder();
        bst.delete(2);
        System.out.println("-------------");
        bst.printInOrder();
    }
}
